package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/11/25.<br><br>
 *
 * 中等：搜索二维矩阵
 */
public class Topic74 {

    public static void main(String[] args) {
        Topic74 instance = new Topic74();
        int[][] array;

        array = new int[][] {
                {1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 60}
        };
        System.out.println(instance.searchMatrix(array, 3));
        System.out.println(instance.searchMatrix(array, 13));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int lowIndex = helper1(matrix, target);
        if(lowIndex < 0) {
            return false;
        }

        return helper2(matrix[lowIndex], target);
    }

    private int helper1(int[][] matrix, int target) {
        int low = -1;
        int high = matrix.length - 1;

        while (low < high) {
            int mild = (high - low + 1) / 2 + low;
            if(matrix[mild][0] <= target) {
                low = mild;
            }
            else {
                high = mild - 1;
            }
        }

        return low;
    }

    private boolean helper2(int[] row, int target) {
        int low = 0;
        int high = row.length - 1;

        while (low <= high) {
            int mild = (high - low) / 2 + low;
            if(row[mild] == target) {
                return true;
            }
            else if(row[mild] > target) {
                high = mild - 1;
            }
            else {
                low = mild + 1;
            }
        }

        return false;
    }
}
